package main

import (
	"fmt"
	"math/rand"
	"time"
)

func main()  {

	slice := generateSlice(10)
	//slice := []int{10, 9, 8 ,7}
	fmt.Println("\n--- Unsorted --- \n\n", slice)

	bubbleSort(slice)
	//quickSort(slice, 0, 9)
	//insertSort(slice)

	fmt.Println("\n--- Sorted ---\n\n", slice)
}

/*
	4、冒泡排序法
	时间复杂度：O(n2)
	稳定性：稳定

*/

func bubbleSort(slice []int) {
	len := len(slice)

	swapped := true;
	for {

		swapped = false

		for i := 1; i < len; i++ {
			if slice[i - 1] > slice[i] {
				swap(slice, i - 1, i)
				swapped = true
			}
		}

		if swapped {
			break
		}

	}
}


/*
	3、快速排序法
	时间复杂度：On(logn)
	稳定性：不稳定

*/

func partition(slice []int, l int, r int) int {

	v := slice[l]

	j := l
	for i := l + 1; i <= r; i++ {
		if slice[i] < v {
			swap(slice, j + 1, i)
			j++
		}
	}
	
	swap(slice, l, j)
	return j
}

func quickSort(slice []int, l int, r int)  {

	if l >= r {
		return
	}

	p := partition(slice, l, r)
	quickSort(slice, l, p - 1)
	quickSort(slice, p + 1, r)
}



/*
	2、插入排序法
	时间复杂度：O(n2)
	稳定性：稳定
	优点：数组基本有序的情况下，效率非常高

*/

func insertSort(slice []int)  {

	len := len(slice)
	for i := 1; i < len; i++ {

		for j := i; j > 0 && slice[j] < slice[j-1]; j-- {
			swap(slice, j, j-1)
		}
	}
}

/*
	1、选择排序法 （直接选择排序）
	时间复杂度：O(n2)
	优点：比冒泡排序交换次数少
	稳定性：不稳定
*/

func selectionSort(slice []int) {

	len := len(slice)
	for i := 0; i < len; i++ {
		minIndex := i
		for j := i + 1; j < len; j++ {
			if slice[j] < slice[minIndex] {
				minIndex = j
			}
		}

		swap(slice, i, minIndex)

	}
}


func generateSlice(size int) []int {

	slice := make([]int, size, size)
	rand.Seed(time.Now().UnixNano())
	for i := 0; i < size; i++ {
		slice[i] = rand.Intn(999) - rand.Intn(999)}

	return slice
}


func swap(slice []int, i int, j int) {
	if i == j {
		return
	}

	slice[i], slice[j] = slice[j], slice[i]
}